package org.niuke.sort;

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 请实现无重复数字的升序数组的二分查找
     *
     * 给定一个 元素升序的、无重复数字的整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标（下标从 0 开始），否则返回 -1
     * 
     * @param nums int整型一维数组 
     * @param target int整型 
     * @return int整型
     */
    public int search (int[] nums, int target) {
        // write code here
        if (nums.length == 0) {
            return -1;
        }
        int start = 0;
        int end = nums.length - 1;
        while (start <= end) {
            int index = (end - start) / 2 + start;
            if (nums[index] < target) {
                start = index + 1;
            } else if (nums[index] == target) {
                return index;
            } else {
                end = index - 1;
            }
        }
        return -1;
    }



    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * BM19 寻找峰值
     *
     * @param nums int整型一维数组
     * @return int整型
     */
    public int findPeakElement (int[] nums) {
        // write code here
        int end = nums.length - 1;
        int start = 0;
        int index = (end - start) / 2 + start;
        while (index < nums.length || index > 0) {
            boolean up = index + 1 >= nums.length || nums[index] > nums[index + 1];
            if (up) {
                boolean down = index - 1 < 0 || nums[index] > nums[index - 1];
                if (down) {
                    return index;
                }else {
                    end = index - 1;
                }
            }else {
                start = index + 1;
            }
            index = (end - start) / 2 + start;
        }
        return index;
    }


    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * BM20 数组中的逆序对
     *
     * @param nums int整型一维数组
     * @return int整型
     */
    int count = 0;
    public int InversePairs (int[] nums) {
        // write code here
        if (nums.length < 2) {
            return 0;
        }
        mergSort(nums, 0, nums.length - 1);
        return count;
    }

    private void mergSort(int[] arrs, int left, int right) {
        int mid = (right - left) / 2 + left;
        if (left < right) {
            mergSort(arrs, left, mid);
            mergSort(arrs, mid + 1, right);
            merg(arrs,left,mid,right);
        }
    }

    private void merg(int[] arrs, int left, int mid, int right) {
        int[] temp = new int[right - left + 1];
        int l = left;
        int ls = left;
        int r = mid +1;
        int c = 0;
        while (l <= mid && r <= right) {
            if (arrs[l] < arrs[r]) {
                temp[c] = arrs[l];
                l++;
                c++;
            } else {
                temp[c] = arrs[r];
                count += (mid - left + 1);
                count %= 1000000007;
                r++;
                c++;
            }
        }
        while (l <= mid) {
            temp[c] = arrs[l];
            l++;
            c++;
        }
        while (r <= right) {
            temp[c] = arrs[r];
            r++;
            c++;
        }
        for (int i : temp) {
            arrs[ls++] = i;
        }
    }
}